Programs are created by individuals referred to herein as code producers and run by individuals referred to herein as code consumers. The code consumer does not want to run an untrusted program created by the code producer because the program communicates with the code consumer's computer via a runtime library, which provides functions to access resources such as files and the network. The code consumer wants to be sure that the program is safe, meaning that it does not corrupt user data, it does not export private data to outside sources, and it does not abuse system resources.
There are several existing methods for ensuring safety of a computer program. These include dynamic checking; and static checking. Dynamic checking refers to the process by which each potentially unsafe operation is checked just before it occurs. For example, if a safety policy forbids access to a particular directory, then the runtime (RT) library or RT monitor must check each file access. Dynamic checking has advantages. First, it is precise. That is, it only detects safety violations that the program is actually going to commit. If the checker detects a violation, then the program would actually commit the violation had the user turned off the checker. Second, it is simple. The entire checker consists of simple checks that are placed in the runtime library alongside the appropriate routines. However, dynamic checking has disadvantages. First, it is late because it detects errors at the last possible moment. Lateness is a problem because terminating the program without warning may surprise or confuse the user or cause her to lose valuable data. Also, when terminating the program, it may be difficult to recover operating system (OS) resources that the program has allocated, which may adversely affect the performance of other running programs. Second, dynamic checking is inefficient. Since every operation performs a check before executing, these checks occupy a considerable portion of CPU time.
In static checking, the entire program is analyzed before execution to see whether it is safe. Static checking has advantages. First, static checking is early in that it detects all faults before execution begins. Thus, if the checker verifies the program, no runtime errors can occur, so the user cannot lose data, and the OS never has to terminate the program. Second, static checking is efficient. All checking is done based on the program text, so there are no runtime checks whatsoever, and the program can run at the same speed as a fully trusted program. Static checking also has disadvantages. First, static checking is complex, because it tries to reason about program behavior, which is complex. Second, static checking is incomplete, meaning that it rejects some safe programs. This imprecision comes from two sources. First, programs are complex. Although the checker may be able to handle many simple programs, because many program properties of practical interest are undecidable, there are some safe programs that it cannot verify. Second, the static checker runs with incomplete information in that it knows the program but it does not know its input. The best result state checking can produce is to determine whether some input causes an unsafe action. It cannot determine whether this input actually occurs.
In the context of resource usage, dynamic checking refers to the process by which a resource manager performs checks while the program runs, while static checking refers to the process by which the resource manager performs checks before the program runs. Dynamic checking is flexible but inefficient, while static checking is efficient but inflexible.
Resource use estimation in programs may be considered a problem for estimating execution times of sequential computer programs. Execution time itself can be considered a resource where the basic consumption of each instruction is 1. In contrast, the resource usage of a computer program is often parameterized by the variables of the program. For example, consider the following code fragment:
for (i = 0; i < n; ++i) {// Write i bytes to filefile.write (buffer, i);}
The execution time problem for this code looks only at the top level “for” construct and has to analyze the sum Σi=1n 1. In contrast, in order to evaluate the resource usage of this program, the sum Σi=1n i is analyzed. Thus, the execution time problem is a special case of the resource usage problem.
For more information on static resource accounting, see A. Ermedahl and J. Gustafsson, Deriving Annotations for Tight Calculation of Execution Time, In Proceedings of Euro-Par'97, Vol. 1300 of Lecture Notes in Computer Science, pp. 1298-1307, August 1999.
With respect to dynamic approaches, a dynamic resource monitor is used to keep track of all resource usage and can be very inefficient. For more information on dynamic resource accounting, see C. Park and A. Shaw, Experiments with a Program Timing Tool Based on Source-level Timing Schema, IEEE Transactions on Computers, 24:48-57, May 1991.